ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/tsql/doc/tsql.mail/[e-mail]…s64.cineca.it _Wed Jun 9 11:00:17 1993.msg

Internet Message Format | 1996-01-31 | 38KB

Received: from icineca.cineca.it by optima.CS.Arizona.EDU (5.65c/15) via SMTP
    id AA03501; Wed, 9 Jun 1993 01:58:14 MST
Received: from deis64.cineca.it by ICINECA.CINECA.IT (IBM VM SMTP V2R2)
   with TCP; Wed, 09 Jun 93 10:58:31 SET
Received: from [137.204.57.79] (deis79) by deis64.cineca.it (4.1/SMI-4.1)
    id AA15151; Wed, 9 Jun 93 11:00:16 +0200
Date: Wed, 9 Jun 93 11:00:17 +0100
From: (Fabio Grandi) <[e-mail]>
Message-Id: <[e-mail]>
To: [e-mail]
Cc: [e-mail]
Subject: Benchmark Queries (Classes O1.S5, O1.S6, O2.S7, O2.S8, O3.S9, O3.S10)

Dear Christian:

please find included our benchmark queries.

Each class follows the header:
" %%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ".

We also wrote explanations for each query,
in order to make clear our categorization choices.
We tried to explicit all the selection conditions
which are often implicit in the English formulation
(or depend on the level of detail adopted in categorization).
Feel free to throw explanations out,
if you consider any of them unnecessary.

We didn't repeat categories for a single query,
but we explained how many and which predicates fit in each one.

Please, if possible, use for the authors' address list
of the benchmark paper the following affiliation of ours:
Dip. di Elettronica Informatica e Sistemistica,
Universit\`a di Bologna, Italy

Sincerely,
    Fabio, Rita and Paolo.

LaTeX source follows:
=====================================================================

\documentstyle[11pt]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% VARIOUS MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\addtolength{\textwidth}{1.485in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\addtolength{\topmargin}{-.85in}
\addtolength{\textheight}{1.8in}

\newcommand{\autsp}{$\;\;\;$}
\long\def\query#1#2#3{\begin{verse} {\bf Query \no} {#1} \end{verse} \begin{verse} {\bf Answer:} {#2} \end{verse} \begin{verse} {\bf Category:} {#3} \end{verse}}
\newcounter{qnumber}
\newcounter{rnumber}[subsection]
\newcounter{gnumber}[subsubsection]
\newcommand{\no}{\setcounter{qnumber}{\value{subsection}} \setcounter{rnumber}{\value{subsubsection}}\protect\refstepcounter{gnumber} Q \protect\theqnumber.\protect\thernumber.\protect\thegnumber:}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PAPER START
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{\Large{\bf The TSQL Benchmark} \\
       Query Classes: O1.S5, O1.S6, O2.S7, O2.S8, O3.S9, O3.S10}
\author{Fabio Grandi \autsp Maria Rita Scalas \autsp Paolo Tiberio}
\date{}
\maketitle

\section{The Benchmark Queries}

\subsection{Explicit-attribute Output}

This section involves queries which return only explicit-attribute
values---no valid-time values are present in the result.



%%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Class O1.S5 (Other, Event, Computed)}

%%% 01.S5 %%% Q#1 %%%
\query{Find Ed's skills when he joined the Book department}
  {``typing,'' ``filing'' and ``driving.''}
  {(Projected, None) /
   (Containment, Event, Computed) /
   (=, Constant)}

  \noindent {\it The employee with name Ed joined the Book department
    on 4/1/87, when he was qualified for typing, filing and driving.

    The category
    ``(Containment, Event, Computed)'' indicates that a containment
    based predicate is used to select skill data containing
    an event-valued argument (i.e. 4/1/87) which is derived from the
    valid-times of stored facts (begin of the valid-times Ed was
    at the Book department).  Finally, ``(=, Constant)'' indicates
    that there are only non-temporal selection predicates
    that test for equality of an attribute value with a constant
    (i.e., the name of the person is Ed both in employee and in skills data,
    and the department of the person in employee data is Book).
    }

%%% 01.S5 %%% Q#2 %%%
\query{Find the name and the budget of Ed's departments when he joined them}
  {``(Toy, \$150K)'' and ``(Book, ---).''}
  {(Projected, None) /
   (Containment, Event, Computed) /
   (=, Constant) (=, Foreign)}

  \noindent {\it Ed joined the Toy department on 2/1/82, when the budget
    was \$150K, and the Book department on 4/1/87. No information about
    the Book budget is available.

    The valid-time selection is categorized as ``(Containment, Event,
    Computed)'' since it checks whether the valid-times of selected budget data
    contain an event-valued argument computed from employee data
    (the date Ed joined a department).
    A non-temporal selection predicate --- in the category ``(=, Constant)'' ---
    is used to select the department names and
    the periods in which Ed was in a department.
    A non-temporal predicate --- in the category ``(=, Foreign)'' ---
    is used to select the budget of that
    department, via the join condition {\tt dept.Department=employee.Dept}.
    }

%%% 01.S5 %%% Q#3 %%%
\query{Find all the data and the skills of the employees
  of the Toy department when it opened}
  {``(Di, \$30K, Toy, F, 10/1/60, directing).''}
  {(Complete, None) /
   (Containment, Event, Computed) /
   (=, Constant) (=, Foreign)}

  \noindent {\it The Toy department opened on 1/1/82. On that date,
    only Di worked in it. She was qualified for directing only.

    The result is composed of all the non-temporal attributes
    retrieved from the relations employee and skills according
    to the output category ``(Complete, None)''.
    In both relations, data are selected if their valid-times contain
    the event ``opening of the Toy department'', according to
    two selection clauses in the category ``(Containment, Event, Computed)''.
    Additional non-temporal conditions are imposed to the selected data in either relations:
    ``(=, Constant)'' indicates the selection of the employees working in the Toy department;
    ``(=, Foreign)'' indicates the selection of the skills of such employees.
    Another predicate of the class ``(=, Constant)'' is used to determine the event
    ``opening of the Toy department'' as the beginning of the temporal element
    in which Toy data are stored in relation {\tt dept}.
    }

%%% 01.S5 %%% Q#4 %%%
\query{Find the names of the employees who had been working in the Toy
  department before the budget was decreased}
  {``Ed.''}
  {(Projected, None) /
   (Ordering, Event, Computed) (Ordering, Interval, Computed) /
   (=, Constant) ($<>$, Constant)}

  \noindent {\it The budget of the Toy department was decreased on 1/1/87.
    Ed is the only employee who had been working in it before that date.

    The temporal selection predicate used for categorization is
    ``(Ordering, Event, Computed)''. It indicates that an ordering based
    predicate is used to select employee data with valid-times preceding
    an event-valued argument (i.e. 1/1/87) which is derived from stored facts.
    A predicate in the category ``(=, Constant)'' is used to select an employee
    working in the Toy department.
    The other temporal predicate --- categorized as ``(Ordering, Interval, Computed)''
    --- selects two adjacent versions of department data, testing if
    their valid-time intervals meet.
    Furthermore, non-temporal predicates are used to determine such versions.
    ``(=, Constant)'' also indicates that the two versions must have the same
    department name: ``Toy.''
    ``($<>$, Constant)'' indicates that a test must be effected on the decreasing
    value of the budget data between the two versions.
    }

%%% 01.S5 %%% Q#5 %%%
\query{Find Ed's skills when his salary increased from \$30K to \$40K}
  {``typing,'' ``filing'' and ``driving.''}
  {(Projected, None) /
   (Containment, Event, Computed) (Ordering, Interval, Computed) /
   (=, Constant)}

  \noindent {\it Ed had typing, filing and driving skills when his salary
    was increased from \$30K to \$40K on 2/1/86.

    The query is categorized as ``(Containment, Event, Computed)''
    since it selects skills data having valid times containing the event 2/1/86
    which is computed from other data.
    Such an event is determined considering  the two consecutive versions of
    data for the employee ``Ed'',
    and extracting the beginning of the second versions.
    The versions can be determined as follows: a first predicate in category
    ``(=, Constant)'' selects one Ed's version (with salary \$30K);
    two predicates in the categories ``(=, Constant)'' and
    ``(Ordering, Interval, Computed)'' select the Ed's version
    (with salary \$40K) that follows the first one.
    A third non-temporal predicate ``(=, Constant)'' selects Ed's data
    in relation {\tt skills}.
    }



%%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Class O1.S6 (Other, Event, Other)}

%%% 01.S6 %%% Q#1 %%%
\query{Find the current Toy department data}
  {``(Toy, Di, \$100K).''}
  {(Complete, None) /
   (Containment, Event, Explicit) /
   (=, Constant)}

  \noindent {\it The current manager and budget of the Toy department
    are Di and \$100K, respectively.

    The temporal selection predicate
    ``(Containment, Event, Explicit)'' selects the department data whose
    valid-time includes the explicit event ``now.''
    A non-temporal predicate in the category ``(=, Constant)'' selects Toy data.
    }

%%% 01.S6 %%% Q#2 %%%
\query{Find the skills for which Ed was qualified after 1/1/83}
  {``filing'' and ``driving.''}
  {(Projected, None) / (Ordering, Event, Explicit) / (=, Constant)}

  \noindent {\it Ed was qualified for filing on 1/1/85 and
    for driving (for the second time in his career) on 6/1/84.
    The valid-time selection predicate ``(Ordering, Event, Explicit)''
    compares the valid-time of Ed's skills with the explicitly supplied
    event 1/1/83. The non temporal predicate selects Ed's data in the
    skills relation.
    }

%%% 01.S6 %%% Q#3 %%%
\query{Find Di's salary on her 25$^{th}$ birthday}
  {``\$40K.''}
  {(Projected, None) /
   (Containment, Event, User-defined) /
   (=, Constant)}

  \noindent {\it The date of Di's 25$^{th}$ birthday is 10/1/85.
    At that time her salary was \$40K.

    The valid-time selection embedded in the query is categorized as
    ``(Containment, Event, User-defined),'' since it selects employee data
    whose valid-time contains an event computed from the user-defined
    time attribute {\tt D-birth}. Two non-temporal selections in the category
    ``(=, Constant)'' are used to select employees whose name is ``Di''
    (once to select her {\tt D-birth} and once to select her {\tt Salary}).
    }

%%% 01.S6 %%% Q#4 %%%
\query{Find the departments Ed worked in before and not after 1/1/88}
  {``Toy.''}
  {(Projected, None) /
   (Ordering, Event, Explicit) /
   (=, Single)(=, Constant)}

  \noindent {\it
    Before 1/1/88 Ed  worked only in the Toy department (from 2/1/82 to 1/31/87).

    The query can be answered in two steps.
    At first, the names of all the departments Ed worked in
    are selected by means of a ``(=, Const)'' non-temporal predicate.
    In the second step, each name is used to find out the temporal element
    in which Ed worked in such a department by means of
    a ``(=, Single)'' non-temporal predicate.
    Finally, the department name is retrieved only if the temporal element precedes
    the event-valued constant 1/1/88
    according to an ``(Ordering, Event, Explicit)'' temporal selection predicate.
    }

%%% 01.S6 %%% Q#5 %%%
\query{Find the name and date of birth of the women who were working
  in the Toy department on 1/1/83}
  {``(Di, 10/1/60).''}
  {(Projected, None) /
   (Containment, Event, Explicit) /
   (=, Constant)}

  \noindent {\it The only woman working in Toy department on 1/1/83 was Di.
    Di was born on 10/1/60.

    The categorization of the query as ``(Containment, Event, Explicit)''
    indicates that employee data are selected if their valid-times contain
    the event 1/1/83, explicitly supplied in the query.
    Furthermore, the non-temporal clause selects only female employees
    working in the Toy department.
    }

\subsection{Valid-time Output}

This section involves queries which return only valid-time
values---no explicit-attribute values are present in the result.



%%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Class O2.S7 (Other, Interval, Computed)}

%%% 02.S7 %%% Q#1 %%%
\query{Find when the Toy budget decreased}
  {``1/1/87.''}
  {(None, Not Empty) /
   (Ordering, Interval, Computed) /
   (=, Constant) ($<>$, Single)}

  \noindent {\it The budget of the Toy department decreased on 1/1/87.

    The required date is extracted when two consecutive periods are found
    (i.e. selected via the predicate ``(Ordering, Interval, Computed)'')
    in the first of which the budget of the Toy department was higher than in the second one
    (as tested by ``($<>$, Single)''). The category ``(=, Constant)'' indicates
    that Toy data are selected in relation {\tt dept} via a non-temporal
    predicate testing the equality of the key with a constant.
    The required date is extracted as the beginning of the valid-time of the
    second period.
    }

%%% 02.S7 %%% Q#2 %%%
\query{Find when the name of an employee was presumably changed}
  {``1/1/88.''}
  {(None, Not Empty) /
   (Ordering, Interval, Computed) /
   (=, Single) ($<>$, Single)}

  \noindent {\it
    Only ED's name changed from Ed to Edward on 1/1/88.

    We can guess that employees with different names but
    with the same gender and date of birth are the same person
    (also the salary and the department before and after the name
    change can be tested for equality, but their values could
    have been changed together with the name).
    The retrieved event is the validity beginning of the second
    of two consecutive employee versions.
    Such versions are detected by means of the following conditions:
    their valid-time intervals meet (cf. ``(Ordering, Interval, Computed)''),
    their time-invariant attributes but the name are equal
    (cf. ``(=, Single)'' used twice), their names are different
    (cf. ``($<>$, Single)'').
    }

%%% 02.S7 %%% Q#3 %%%
\query{Find when the salary of a manager increased}
  {``8/1/84'' and ``9/1/86.''}
  {(None, Not Empty) /
   (Ordering, Interval, Computed)
   (Containment, Element, Computed) /
   (=, Foreign) (=, Const) ($<>$, Single)}

  \noindent {\it The only manager in our data is Di.
    Di's salary was increased on 8/1/84 and on 9/1/86.

    First, all the manager names (together with the valid-times
    they were manager) are retrieved from the relation {\tt dept}
    by means of a simple projection.
    Then, the data of each manager are selected in the relation {\tt emp} by means of
    a non-temporal predicate in the class ``(=, Foreign)'' and a valid-time
    predicate in the class ``(Containment, Element, Computed)''.
    In order to find the desired events, two consecutive versions of the data
    of a manager with increasing salary must be detected.
    The desired dates are extracted as the begin of the valid-time
    interval of the second version.
    A version of the manager data is selected via the ``(=, Foreign)'' predicate
    as a candidate to be the first desired version.
    The second version is selected in relation {\tt emp} if
    its valid-time interval is met by the valid-time interval of the
    first version (temporal selection in
    category ``(Ordering, Interval, Computed)''),
    has the same {\tt Name} and has a greater {\tt Salary} than the first version
    (non-temporal selection with categories ``(=, Constant)''
    and ``($<>$, Single)'').
    Notice that, if the name equality for the second version is tested
    with the names retrieved from {\tt dept}
    rather than with the name in the first selected version, two predicates
    of the class ``(=, Foreign)'' are used and ``(=, Constant)''
    is no longer present in the categorization.
    }

%%% 02.S7 %%% Q#4 %%%
\query{Find the periods in which Di earned \$40K while
  she was manager of the Toy department}
  {``8/1/84 -- 8/31/86.''}
  {(None, Not Empty) /
   (Containment, Interval, Computed) /
   (=, Constant)}

  \noindent {\it DI has been manager of the Toy department since 1982.
    In this period, she earned \$40K from 8/1/84 to 8/31/86.

    The query selects the valid-time intervals --- of the employee
    data with name ``Di'' and salary \$40K, according to
    ``(=, Constant)'' non-temporal selection --- completely contained in another
    interval computed from other data, according to
    a ``(Containment, Interval, Computed)'' predicate.
    Such an interval is the valid time she was manager of the Toy department
    and is selected from the relation {\tt dept} via a non-temporal predicate
    in the category  ``(=, Const)''
    concerning the {\tt Manager} attribute value.
    }

%%% 02.S7 %%% Q#5 %%%
\query{Find the acquisition dates of the skills Ed had during the year
  he joined the Toy department}
  {``1/1/82'' and ``4/1/82.''}
  {(None, Not Empty) /
   (Containment, Interval, Computed) /
   (=, Constant)}

  \noindent {\it Ed joined the Toy department on 2/1/82. During 1982,
    he acquired a driving skill on the  1$^{st}$ of January,
    and a typing skill on the  1$^{st}$ of April.

    The year 1982 is computed from the beginning of the temporal element
    Ed worked in the Toy department, which is selected by means
    of non-temporal predicates in the category ``(=, Constant).''
    Hence, the Ed's skills (selected by another
     ``(=, Constant)'' predicate) whose valid-times overlap the computed year
    are retrieved according to a ``(Containment, Interval, Computed)''
    temporal selection predicate.
    }



%%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Class O2.S8 (Other, Interval, Other)}

%%% 02.S8 %%% Q#1 %%%
\query{Find the beginning of the period which includes the year 1989
  and in which Edward had a constant salary.}
  {``1/1/88.''}
  {(None, Not Empty) /
   (Containment, Interval, Explicit) /
   (=, Constant)}

  \noindent {\it Edward has got a constant salary since 1/1/88.
    As this period includes 1989, 1/1/88 is the answer.

    Assuming that valid-time intervals of employee data with a constant salary
    can be extracted from the relation {\tt employee}
    (it can be noticed that, if the relation is stored by means
    of temporally homeogeneous tuples, the employee histories must be {\bf coalesced}
    after projection on {\tt salary} in order to obtain maximal intervals
    in which the salary has not been changed),
    those concerning Edward can be selected via a ``(=, Constant)'' predicate.
    The query retrieves the beginning of the computed period which contain
    the explicit interval 1/1/89 -- 12/31/89, according to a
    ``(Containment, Interval, Explicit)'' temporal predicate.
    }

%%% O2.S8 %%% Q#2 %%%
\query{Find the dates Ed acquired a skill before or after years 1984--1985.}
  {``1/1/82'' and ``4/1/82.''}
  {(None, Not Empty) /
   (Ordering, Interval, Explicit) /
   (=, Constant) }

  \noindent {\it
    Before or after years 1984--1985, Ed acquired a skill on 1/1/82 (driving)
    and on 4/1/82 (typing).

    The beginning of the valid-times of Ed's skills are selected if they
    precede or follow the explicit interval ``1/1/84 -- 12/31/85,''
    according to the category ``(Ordering, Interval, Explicit).''
    A non-temporal predicate in the category ``(=, Constant)''
    is used to select Ed's data in relation {\tt skills}.
    }

%%% 02.S8 %%% Q#3 %%%
\query{Find ED's unemployment periods when he was not 30 years old}
  {``1/31/87 -- 1/4/87.''}
  {(None, Not Empty) /
   (Ordering, Interval, User-defined) (Containment, Interval, User-defined) /
   (=, Constant)}

  \noindent {\it
    ED has been 30 years old from 7/1/85 to 6/30/86.
    Before 7/1/85 or after 6/30/86,
    he was unemployed from 1/31/87 to 1/4/87.

    The query is categorized as ``(Ordering, Interval, User-defined)''
    because valid-times of data are selected if they precede or follow an
    interval which is computed from user-defined times stored in other data,
    that is 7/1/85 -- 6/30/86.
    The other temporal predicate, in the category
    ``(Containment, Interval, User-defined),'' is used because valid-times qualify
    for the query also when they overlap the interval 7/1/85 -- 6/30/86 without
    being completely contained in it. In this case, only the portion of the qualifying
    intervals outside 7/1/85 -- 6/30/86 must be retrieved.
    Non-temporal predicates in the category ``(=, Constant)'' are used
    to restrict {\tt employee} to ED's data ({\tt Name="Ed"} or {\tt Name="Edward"}),
    and to find out the periods in which he was unemployed
    (e.g. testing for null values of his department
    and salary; for the problem of coalescing intervals, see the discussion
    of query {Q \theqnumber.\thernumber.1}).
    The restriction to ED's data also allows the determination of
    his date of birth which is used for the temporal selection.
    }

%%% 02.S8 %%% Q#4 %%%
\query{Find the period in which Di worked in the department
  in which she has been working during the whole 1987}
  {``1/1/82 -- now.''}
  {(None, Not Empty) /
   (Containment, Interval, Explicit) /
   (=, Constant)}

  \noindent {\it Di worked in Toy department during 1987.
    She has worked in that department from 1/1/82.

    The category ``(Containment, Interval, Explicit)'' indicates that
    a containment-based predicate is used to select employee data
    whose valid-times contain the user-supplied interval ``1/1/87 -- 12/31/87.''
    As in Query {Q \theqnumber.\thernumber.1}, we assume that periods in which an employee worked
    in the same department can be determined.
    Di's data are selected via a ``(=, Constant)'' non-temporal predicate.
    If the containment test succeds, the entire element-valued valid-time
    argument of the predicate is retrieved.}

%%% 02.S8 %%% Q#5 %%%
\query{Find all the dates from 1/1/83 to 12/31/85 at which
  the Toy department budget changed}
  {``8/1/84.''}
  {(None, Not Empty) /
   (Containment, Interval, Explicit) (Ordering, Interval, Computed) /
   (=, Single) ($<>$, Single)}

  \noindent {\it
    From 1/1/83 to 12/31/85, the Toy budget changed only on 8/1/84.

   In this query, there are two valid-time selection  predicates.
   The one used for categorization is ``(Containment, Interval, Explicit)''
   and selects the dates of interest by means of their containment in an interval
   explicitly supplied in the query.
   The other one, ``(Ordering, Interval, Computed),'' is used to determine two
   consecutive versions of department data, testing if their valid-time intervals meet.
   The non-temporal predicates are also used for their determination:
   the two versions must have the same department name --- according to ``(=, Single)''
   --- and different salary values --- according to ``($<>$, Single)''.
   }

\subsection{Explicit-attribute and Valid-time Output}

The output from queries in this section contains explicit attribute
values with associated valid times.



%%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Class O3.S9 (Other, Element, Computed)}

%%% 03.S9 %%% Q#1 %%%
\query{Find Ed's salary history when he had a driving skill}
  {``(\$20K, 2/1/82 -- 5/1/82),''
   ``(\$30K, 6/1/84 -- 1/31/85)'' and
   ``(\$40K, 2/1/85 -- 1/31/87 $\cup$ 4/1/87 -- 12/31/87)''}
  {(Projected, Not Empty) /
   (Containment, Element, Computed) /
   (=, Constant)}

  \noindent {\it Ed has been qualified for driving from 2/1/82 to 5/1/82
    and from 6/1/84 to 12/31/87 (after that, Edward nor Ed had).
    In those periods, he earned \$20K from 2/1/82 to 5/1/82,
    \$30K from 6/1/84 to 1/31/85 and \$40K from 2/1/85 to 1/31/87
    and from 4/1/87 to 12/31/87.

    A non-temporal ``(=, Constant)'' is used to select Ed's data in
    relation {\tt emp}.
    Ed's salary data are retrieved if their valid-times are contained
    in an element-valued period computed from stored facts, according
    to ``(Containment, Element, Computed)''.
    Such period is computed by means of other ``(=, Constant)'' predicates
    which select data with {\tt Name="Ed"} and {\tt Skill="driving"}
    in relation {\tt skills}.
    }

%%% 03.S9 %%% Q#2 %%%
\query{Find the salary history, during the periods in which ED
  had a driving skill, of the employees who earned less than \$50K in 1989}
  {``(---, 1/1/82 -- 1/31/82),''
   ``(\$20K, 2/1/82 -- 5/1/82),''
   ``(\$30K, 6/1/84 -- 1/31/85),''
   ``(\$40K, 2/1/85 -- 1/31/87),''
   ``(---, 1/31/87 -- 3/30/87)'' and
   ``(\$40K, 4/1/87 -- 5/31/88).''}
  {(Projected, Not Empty) /
   (Containment, Element, Computed)
   (Containment, Interval, Explicit) /
   (=, Constant) ($<>$, Constant)}

  \noindent {\it ED was qualified for driving from 1/1/82 to 5/1/82 and
    from 6/1/84 to 5/31/88.
    The only employee who earned less than \$50K in 1989 is ED again.
    While he had the driving skill, his salary was
    \$20K from 2/1/82 to 5/1/82,
    \$30K from 6/1/84 to 1/31/85,
    \$40K from 2/1/85 to 1/31/87 and from 4/1/87 to 5/31/88
    (unknown from 1/1/82 to 1/31/82 and from 1/31/87 to 3/30/87).

    Two valid-time selection predicates are present in the query.
    One --- ``(Containment, Interval, Explicit)'' --- is used
    to select the objects of interest, whereas the other
    --- ``(Containment, Element, Computed)'' --- is used
    to select a portion of their data history.
    Objects qualify if the salary is less that \$50K (cf. ``($<>$, Constant)'')
    in their employee data selected by the temporal predicate
    ``(Containment, Element, Computed),'' extracting
    the versions with valid-times overlapped by the user-supplied interval
    ``1/1/89 -- 12/31/89''.
    The other non-temporal predicate is used to evaluate
    the element-valued period in which ED had the driving skill
    (cf. ``(=, Constant)'' testing for {\tt skills.Name} equal to ``Ed'' or ``Edward'').
    Such period is used as argument by the temporal predicate used for categorization.
    }

%%% 03.S9 %%% Q#3 %%%
\query{Find the name and salary history of the male employees
  in the periods they were directed by a woman}
  {``(\$20K, 2/1/82 -- 5/31/82),'' and
   ``(\$30K, 6/1/82 -- 1/31/85).''
  }
  {(Projected, Not Empty) /
   (Containment, Element, Computed)
%   (Containment, Interval, Computed)
%   (Containment, Interval, Computed)
%   (Containment, Interval, Computed) /
   (=, Constant) (=, Foreign)}

  \noindent {\it The only employee qualifying for the query is Ed,
    since he had been directed by Di when he worked in the Toy department
    from 2/1/82 to 1/31/87.
    His salary history in that period is:
    \$20K from 2/1/82 to 5/31/82, \$30K from 6/1/82 to 1/31/85
    and \$40K from 2/1/85 to 1/31/87.

    The objects of interest for this query are the male employee which can
    be identified by a ``(=, Constant)'' predicate in the relation {\tt emp}.
    The query is categorized as ``(Containment, Element, Computed),''
    since it selects the data of the selectd objects having their valid-times
    contained in an element-valued argument computed from other stored facts.
    In order to find out such an element, two temporal joins must be effected:
    one between the relations {\tt emp} and {\tt dept}, to find out the department data
    of the selected employee, and the other between the relations {\tt dept} and {\tt emp}
    again, to find out the department manager data.
    The two joins can be categorized as ``(=, Foreign)'' and
    ``(Containment, Element, Computed)'', because the join attribute equality and
    the overlap of the valid-times must be ensured.
    The intersection of the valid-times of the histories joined, with the final
    local restriction {\tt emp.Gender=F} on the manager data, gives the
    desired temporal element.
    }

%%% 03.S9 %%% Q#4 %%%
\query{Find the department name, the manager name and the periods, for which
  a department manager earned more than one third of the department budget}
  {``(Toy, Di, 1/1/87 -- now).''}
  {(Projected, Not Empty) /
   (Containment, Element, Computed) /
   ($<>$, Arbitrary)}

  \noindent {\it The only stored information about department managers is that
    Di has directed the Toy department from 1/1/82.
    She earned more than one third of the department budget from 1/1/87 to the present
    (cf. \$50K $>$ \$100K/3).

    For each department, the requested data are retrieved by means
    of a temporal join between relations {\tt dept} and {\tt emp}.
    The categorizations of the temporal join conditions are the following:
    ``(=, Foreign)'' for the equality {\tt emp.Name=dept.Manager},
    ``(Containment, Element, Computed)'' for the overlap of the salary valid-times with
    the valid-times he/she was manager, ``($<>$, Arbitrary)'' for the further comparison
    between department budget and manager salary.
    }

%%% 03.S9 %%% Q#5 %%%
\query{Find the name and the salary history of the employees
  in the periods they earned as much as their managers}
  {``(Ed, \$30K, 6/1/83 -- 7/31/84)'' and ``(Ed, \$40K, 2/1/86 -- 8/31/86).''}
  {(Projected, Not Empty) /
%   (Containment, Element, Computed)
%   (Containment, Element, Computed)
   (Containment, Element, Computed)
   (Containment, Interval, Computed) /
   (=, Foreign) (=, Single) ($<>$, Single)}

  \noindent {\it The only relationship directed-director between employees
    which can be retrieved from the data is Ed-Di, which held
    from 2/1/82 to 1/31/87 at the Toy department.
    Ed earned as much as Di from 6/1/83 to 7/31/84 (\$30K) and
    from 2/1/86 to 8/31/86 (\$40K).

    The query retrieves salary histories of the employees who earned
    as much as the employee who was the manager of the department they worked in.
    Such employees, and the periods of interest, can be selected via a {\bf cyclic}
    temporal join between {\tt emp} and {\tt dept}.
    As a matter of fact, ``(=, Foreign)'' non-temporal predicates allow us
    to express the join conditions {\tt dept.Department=emp.Dept}
    and {\tt emp.Name=dept.Manager} as in Query {Q \theqnumber.\thernumber.3},
    a ``(=, Single)'' non-temporal predicate allows us to express the furter
    join condition on salary equality between employee and manager,
    whereas ``(Containment, Element, Computed)''
    temporal selection predicates allow us to join data versions
    synchronized along valid-time.
    An additional ``($<>$, Single)'' condition is assumed in the last join
    to ensure selected employees do not have the same name as their managers.
    }



%%% Begin of Class: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Class O3.S10 (Other, Element, Other)}

%%% 03.S10 %%% Q#1 %%%
\query{Find the budget history in the period
  from 1/1/82 to 12/31/84 and from 1/1/87 till now
  of the department Ed ever worked in}
  {``(Toy, \$150K, 2/1/82 -- 7/31/84),''
   ``(Toy, \$200K, 8/1/84 -- 12/31/84),''
   ``(Toy, \$100K, 1/1/87 -- now),''
   ``(Book, --- , 1/1/82 -- 12/31/84)'' and
   ``(Book, ---, 1/1/87 -- now).''}
  {(Projected, Not Empty) /
   (Containment, Element, Explicit) /
   (=, Foreign) (=, Constant)
   }

  \noindent {\it Ed worked in the Toy and in the Book department.
    The budget history of the Toy department in the required period is:
    \$150K from 2/1/82 to 7/31/84, \$200K from 8/1/84 to 12/31/84
    and \$100K from 1/1/87 till now.
    The budget history of the Book department in the same period is
    not available from the stored data (we assume ``nulls'' to be retrieved).

    The departments in which Ed ever worked can be found by means of a
    ``(=, Constant)'' predicate on the employee data.
    The collected values are then used to select budget histories in the
    relation {\tt dept} via a ``(=, Foreign)'' predicate.
    Eventually, portions of such histories are selected by means of a
    valid-time predicate categorized as ``(Containment, Element, Explicit)''
    since it exctracts data with valid-times contained in the user-supplied
    temporal element ``1/1/82 -- 12/31/84 $\cup$ 1/1/87 --- now.''
    }

%%% 03.S10 %%% Q#2 %%%
\query{Find the name and the budget history in 1984 and 1987
  of the department being directed by Di}
  {``(Toy, \$150K, 1/1/84 -- 7/31/84),''
   ``(Toy, \$200K, 8/1/84 -- 12/31/84)'' and
   ``(Toy, \$100K, 1/1/87 -- 12/31/87).''}
  {(Projected, Not Empty) /
   (Containment, Element, Explicit) /
   (=, Constant)}

  \noindent {\it
    In the periods from 1/1/84 to 12/31/84 and from 1/1/87 to 12/31/87,
    Di always directed the Toy department.
    The Toy budget was \$150K from 1/1/84 to 7/31/84,
    \$200K from 8/1/84 to 12/31/84
    and \$100K from 1/1/87 to 12/31/87.

    The query is categorized as ``(Containment, Element, Explicit)'' since
    it selects data contained in an element-valued time constant supplied by the user
    (1/1/84 -- 12/31/84 $\cup$ 1/1/87 -- 12/31/87).
    ``(=, Constant)'' indicates the non-temporal selection of the department data
    where the manager is Di.
    }

%%% 03.S10 %%% Q#3 %%%
\query{Find the names of the department where Ed was working
  at the beginning of the years 1986 and 1987,
  and the periods Ed worked there.}
  {``(Toy, 2/1/82 -- 1/31/87).''}
  {(Projected, Not Empty) /
   (Containment, Element, Explicit) /
   (=, Constant)}

  \noindent {\it
    On 1/1/86 and 1/1/87 Ed was working at the Toy department.
    He has been working in that department from 2/1/82 to 1/31/87.

    The query can be answered in two steps.
    First, department names are selected if stored as data concerning Ed
    by means of a ``(=, Constant)'' predicate testing for the employee name.
    Second, the department names are retrieved together with their valid times
    if these contain the explicit element ``1/1/86 $\cup$ 1/1/87'', by using
    a ``(Containment, Element, Explicit)'' valid-time selection predicate.
    }

%%% 03.S10 %%% Q#4 %%%
\query{Find the name of the manager Ed had on 1984's Christmas
  and on his 27$^{th}$ birthday, and the dates he/she began
  to be manager of their department,}
  {``(Di, 1/1/82).''}
  {(Projected, Not Empty) /
   (Containment, Element, User-defined) /
   (=, Constant) (=, Single) (=, Foreign)}

  \noindent {\it
    Ed's 27$^{th}$ birthday was 7/1/82. On 7/1/82 and on 12/25/1984,
    he worked in the Toy department, directed by Di.
    Di started to direct this department on 1/1/82.

    The query contains a ``(Containment, Element, User-defined)'' valid-time
    predicate selecting data whose valid-times contain an element-value argument
    computed from a user-defined time attribute. As a matter of fact, the element
    ``7/1/82 $\cup$ 12/25/1984'' is computed by means of a date explicitly supplied
    in the query and from the Ed's date of birth, selected via a ``(=, Constant)''
    predicate in relation {\tt employee}.
    The first argument used by the valid-time selection predicate is the element-valued
    period in which Ed worked in a department. This period can be evaluated from Ed's data
    by means of a non-temporal selection predicate ``(=, Single)'', which tests
    employee data for a department name, once the department names have been selected.
    Finally, if a department name qualifies, it is used --- via a ``(=, Foreign)''
    predicate and together with the valid-time selection predicate --- to select
    the manager data (name and valid-time) in relation {\tt dept}.
    }

%%% 03.S10 %%% Q#5 %%%
\query{Find the department name, the then manager,
   the modification dates and the new values of the budget
   for every budget change occurred in 1984, 1986 and 1988.}
  {``(Toy, Di, \$200K, 8/1/84).''}
  {(Complete, Not Empty) /
   (Containment, Element, Explicit)
   (Ordering, Interval, Computed) /
   (=, Single) ($<>$, Single)}

  \noindent {\it No data are available about the Book department budget.
    The Toy department budget changed on 8/1/84 and 1/1/87.
    Only the first date qualifies for the query. The manager at this time
    was Di and the new budget value was \$200K.

    The query is classified as ``(Containment, Element, Explicit)''
    because it uses a valid-time predicate to select data whose valid-times
    are contained in an element-valued argument supplied in the query
    (i.e. ``1/1/84 -- 12/31/84 $\cup$ 1/1/86 -- 12/31/86 $\cup$ 1/1/88 -- 12/31/88'').
    Candidate data are snaphots of the department data taken on budget changes.
    Budget changes are detected by means of the comparison of two consecutive
    department data versions.
    The first one can be freely selected, whereas the second one is
    the version of the same department (equality of the key ensured by means
    of a ``(=, Single)'' predicate) that follows the first one (as ensured
    by a temporal ``(Ordering, Interval, Computed)'' predicate).
    The two versions qualify --- and the validity beginning of the second one is
    selected as a candidate date --- if their budget values differ,
    according to a ``($<>$, Single)'' predicate.
    }

\end{document}


%%%%%%%%%%%%%%%%%%%%%
%%% Query template:
%%%%%%%%%%%%%%%%%%%%%

%%% O.S %%% Q# %%%
\query{}
  {``.''}
  {() /
   () /
   ()}

  \noindent {\it
    }